package dp_algorithm.leetcode.medium;

/**
 * @author bruin_du
 * @description 股票的最大利润
 * @date 2022/5/24 15:28
 **/
public class Offer63_MaxProfit {
    public int maxProfit(int[] prices) {
        //方法一:暴力法
        maxProfit1(prices);

        //方法二：动态规划
        return maxProfit2(prices);
    }

    private int maxProfit2(int[] prices) {
        int cost = Integer.MAX_VALUE,maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            cost = Math.min(cost,prices[i]);
            maxProfit = Math.max(maxProfit,prices[i] - cost);
        }
        return maxProfit;
    }

    private int maxProfit1(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = 0; j < prices.length; j++) {
                if(j > i && prices[j] > prices[i])
                    maxProfit = Math.max(maxProfit,prices[j] - prices[i]);
            }
        }
        return maxProfit;
    }
}
